#include <stdio.h>
#include <stdlib.h>
#include "threadtree.h"

void Init(ThreadTree *tree, datatype ref)
{
	tree->node = NULL;
	tree->refvalue = ref;
}

void Create(ThreadTree *tree, char **str)
{
	Create_(tree, &tree->node, str);
}
void Create_(ThreadTree *tree, ThreadTreeNode **node, char **str)
{
	if (**str == tree->refvalue)
		*node = NULL;
	else
	{
		ThreadTreeNode *current = *node;
		current = malloc(sizeof(ThreadTreeNode));
		current->data = **str;
		current->left = current->right = NULL;
		current->ltag = current->rtag = LINK; //标志位初始化为LINK
		*node = current;
		++(*str); //*str 为 char* 类型的指针
		Create_(tree, &current->left, str);
		++(*str);
		Create_(tree, &current->right, str);
	}
}

void CreateInThread(ThreadTree *tree)
{
	ThreadTreeNode *ptr = NULL; // ptr为前驱结点的地址，第一个结点的前驱为空
	CreateInThread_(tree->node, &ptr);
	ptr->right = NULL; //最后一个结点的右子树单独处理
	ptr->rtag = THREAD;
}
void CreateInThread_(ThreadTreeNode *node, ThreadTreeNode **pre)
{
	//关键是明白中序遍历的思想:左孩子 根结点(要把根当作一棵树) 右孩子
	if (node == NULL)
		return;
	//先左孩子
	CreateInThread_(node->left, pre);

	//再根节点
	//像中序遍历打印结点一样,中序遍历打印结点的操作是打印结点的data域,
	//而这里则是让结点的前驱指向pre,而当自己变成pre后,让pre的后继指向结点
	if (node->left == NULL) //如果左子树为空,则建立线索,让其指向前驱结点
	{
		node->ltag = THREAD;
		node->left = *pre;
	}
	if (*pre != NULL && (*pre)->right == NULL) //如果前驱结点的右子树为空,则建立线索,让前驱结点的右子树指向node
	{
		(*pre)->rtag = THREAD;
		(*pre)->right = node;
	}
	*pre = node;

	//最后右孩子
	CreateInThread_(node->right, pre);
}

void CreatePreThread(ThreadTree *tree)
{
	ThreadTreeNode *ptr = NULL;
	CreatePreThread_(tree->node, &ptr);
	ptr->right = NULL; //最后一个结点的右子树单独处理
	ptr->rtag = THREAD;
}
void CreatePreThread_(ThreadTreeNode *node, ThreadTreeNode **pre)
{
	if (node == NULL)
		return;
	if (node->left == NULL)
	{
		node->ltag = THREAD;
		node->left = *pre;
	}
	if (*pre != NULL && (*pre)->right == NULL) //前驱为空只有最开始的一种情况
	{
		(*pre)->rtag = THREAD;
		(*pre)->right = node;
	}
	*pre = node;
	CreatePreThread_(node->left, pre);
	CreatePreThread_(node->right, pre);
}

ThreadTreeNode *First(ThreadTreeNode *node)
{
	if (node == NULL)
		return NULL;
	ThreadTreeNode *current = node;
	while (current->ltag == LINK)
		current = current->left;
	return current;
}

ThreadTreeNode *Last(ThreadTreeNode *node)
{
	if (node == NULL)
		return NULL;
	ThreadTreeNode *current = node;
	while (current->rtag == LINK)
		current = current->right;
	return current;
}

ThreadTreeNode *Next(ThreadTreeNode *root, ThreadTreeNode *cur)
{
	if (root == NULL || cur == NULL)
		return NULL;
	if (cur->rtag == THREAD) //有线索的情况：后继为右子树中保存的结点
		return cur->right;
	return First(cur->right); //无线索的情况：后继为右子树的中序遍历下的第一个结点
}

ThreadTreeNode *Prio(ThreadTreeNode *node, ThreadTreeNode *cur)
{
	if (node == NULL || cur == NULL)
		return NULL;
	if (cur->ltag == THREAD) //有线索情况：前驱为左子树中保存的结点
		return cur->left;
	return Last(cur->left); //无线索情况：前驱为左子树的中序遍历下的最后一个结点
}

void InOrder(ThreadTreeNode *node) //虽然不用递归很方便简单，但是感觉效率不高
{
	ThreadTreeNode *current;

	current = First(node);
	while (current != NULL)
	{
		printf("%c ", current->data);
		current = Next(node, current);
	}
	printf("\n");
}

ThreadTreeNode *Search(ThreadTreeNode *node, datatype key)
{
	if (node == NULL)
		return NULL;

	//与中序遍历的操作差不多
	ThreadTreeNode *current = First(node);
	while (current != NULL && current->data != key)
		current = Next(node, current);
	return current;
}

ThreadTreeNode *Parent(ThreadTreeNode *node, ThreadTreeNode *cur)
{
	if (node == NULL || cur == NULL)
		return NULL;
	if (cur == node)
		return NULL; //树根结点没有父结点

	ThreadTreeNode *current;
	if (cur->ltag == THREAD)
	{
		current = cur->left;
		if (current->right == cur)
			return current;
	}
	else if (cur->rtag == THREAD)
	{
		current = cur->right;
		if (current->left == cur)
			return current;
	}
	current = First(cur);
	current = current->left; //左线索
	if (current != NULL && current->right == cur)
		return current;
	current = Last(cur);
	current = current->right; //右线索
	if (current != NULL && current->left == cur)
		return current;
	return NULL;
}